package main

import "fmt"

// 如何求解迷宫问题

func main() {
	maze := [][]int{
		{1, 0, 0, 0},
		{1, 1, 0, 1},
		{0, 1, 0, 0},
		{1, 1, 1, 1},
	}
	sol := [][]int{
		{0, 0, 0, 0},
		{0, 0, 0, 0},
		{0, 0, 0, 0},
		{0, 0, 0, 0},
	}
	if getPath(maze, 0, 0, sol) {
		printSolution(sol)
	} else {
		fmt.Println("不存在可达的路径")
	}
}

var n = 4

func printSolution(sol [][]int) {
	for i := 0; i < 4; i++ {
		for j := 0; j < n; j++ {
			fmt.Print(sol[i][j], " ")
		}
		fmt.Println()
	}
}

func isSafe(maze [][]int, x, y int) bool {
	return x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1
}

func getPath(maze [][]int, x, y int, sol [][]int) bool {
	if x == n-1 && y == n-1 {
		sol[x][y] = 1
		return true
	}

	if isSafe(maze, x, y) {
		sol[x][y] = 1
		if getPath(maze, x+1, y, sol) {
			return true
		}
		if getPath(maze, x, y+1, sol) {
			return true
		}
		sol[x][y] = 1
	}

	return false
}
